package simple;

/**
 * 你总共有n枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。
 * 阶梯的最后一行 可能 是不完整的。
 *
 * 给你一个数字n ，计算并返回可形成 完整阶梯行 的总行数。
 *
 * 链接：https://leetcode-cn.com/problems/arranging-coins
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class ArrangingCoins {
    /**
     * 这道题的难度在于能不能发现等差数列的存在。
     * 对于k阶需要的硬币数为 [k*(k+1)] / 2
     * */
    class Solution {
        public int arrangeCoins(int n) {
            int l = 1;
            int r = n;
            while(l < r){
                int mid = l + (r-l+1) / 2;
                long l1 = ((long) mid * (mid + 1)) / 2;
                if(l1 < n){
                    l = mid+1;
                }else{
                    r = mid;
                }
            }
            return l;
        }
    }
}
